package com.mlamp.单调栈;

import com.mlamp.排序算法.基础排序;

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;

public class 下一个最大值带环 {

    public static void main(String[] args) {
        int[] ints = new int[]{2, 1, 2, 4, 3};
        ints = 基础排序.generateArray(30);
        int[] result = nextGreaterElements(ints);
        System.out.println(Arrays.toString(result));
        System.out.println(Arrays.toString(nextGreaterElement4(ints)));

    }


    public static int[] nextGreaterElements2(int[] array) {
        int length = array.length;
        int[] result = new int[length];
        Deque<Integer> stack = new ArrayDeque<>();
        for (int i = 2 * length - 1; i >= 0; i--) {
            while (!stack.isEmpty() && stack.peekLast() <= array[i % length]) {
                stack.peekLast();
            }
            result[i % length] = stack.isEmpty() ? -1 : stack.peekLast();
            stack.offer(array[i % length]);
        }
        return result;
    }


    public static int[] nextGreaterElement5(int[] array) {
        int length = array.length;
        int[] result = new int[length];
        Deque<Integer> stack = new ArrayDeque<>();
        for (int i = 2 * length - 1; i >= 0; i--) {
            while (!stack.isEmpty() && stack.peek() <= array[i % length]) {
                stack.pop();
            }
            result[i % length] = stack.isEmpty() ? -1 : stack.peek();
            stack.push(result[i % length]);
        }
        return result;
    }


    public static int[] nextGreaterElement4(int[] array) {
        int length = array.length;
        int[] result = new int[length];
        Deque<Integer> stack = new ArrayDeque<>();
        for (int i = 2 * length - 1; i >= 0; i--) {
            while (!stack.isEmpty() && stack.peek() <= array[i % length]) {
                stack.pop();
            }
            result[i % length] = stack.isEmpty() ? -1 : stack.peek();
            stack.push(array[i % length]);
        }
        return result;
    }


    public static int[] nextGreaterElements(int[] array) {
        int length = array.length;
        int[] result = new int[length];
        Deque<Integer> stack = new ArrayDeque<>();
        for (int i = 2 * length - 1; i >= 0; i--) {
            while (!stack.isEmpty() && stack.peekLast() <= array[i % length]) {
                stack.pollLast();
            }
            result[i % length] = stack.isEmpty() ? -1 : stack.peekLast();
            stack.offerLast(array[i % length]);
        }
        return result;
    }
}
